import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;


class ImpBig implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Topk {
    /**
     * 不算是topk的真正解法
     * @param array
     * @param k
     * @return
     */
    public static int[] topk1(int[] array,int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        //O(n*logN)
        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }
        //O(k*logN)
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    public static int[] topk2(int[] array,int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new ImpBig());
        //O(k*logK)
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }
        //从第k+1个元素开始进行遍历   O((N-K)*logK)
        for (int i = k; i < array.length; i++) {
            //先获取栈顶元素
            int val = queue.peek();
            if(val > array[i]){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        //走到这里队列里面就是前k个最小的元素
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {1,12,23,43,2,65,17,9};
        int[] ret = topk2(array,4);
        System.out.println(Arrays.toString(ret));
    }

}
